/**
 * https://leetcode.cn/submissions/detail/581470912/
 * 128. 最长连续序列
 * Medium, 黄伟杰 2024.11.18
 * 并查集
 */

class UF
{
private:
    vector<int> parent;
    vector<int> size;

public:
    UF(int n) : parent(n), size(n, 1)
    {
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
        }
    }

    void unionSets(int p, int q)
    {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ)
        {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
    }

    int find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    int getMaxConnectSize()
    {
        int maxSize = 0;
        unordered_map<int, bool> roots;
        for (int i = 0; i < parent.size(); i++)
        {
            if (i == parent[i])
            {
                maxSize = max(maxSize, size[i]);
                roots[i] = true;
            }
        }
        return maxSize;
    }
};

class Solution
{
public:
    int longestConsecutive(vector<int> &nums)
    {
        if (nums.empty())
            return 0;

        unordered_map<int, int> map;
        UF uf(nums.size());
        for (int i = 0; i < nums.size(); i++)
        {
            // 存在重复元素，跳过
            if (map.count(nums[i]))
                continue;

            if (map.count(nums[i] - 1))
            {
                uf.unionSets(i, map[nums[i] - 1]);
            }
            if (map.count(nums[i] + 1))
            {
                uf.unionSets(i, map[nums[i] + 1]);
            }
            map[nums[i]] = i;
        }
        return uf.getMaxConnectSize();
    }
};